package com.srunpass.algorithm;

import com.srunpass.utils.ListParseUtil;

import java.util.List;

/**
 * @author srunpass
 * @version Id: 三角最小和, v 0.1 2025/6/5 09:59 srunpass Exp $
 */
public class 三角最小和 {

    public static void main(String[] args) {
        List<List<Integer>> param = ListParseUtil.parseIntegerList("[[1],[2,3],[4,5,6]]");
        System.out.println(min(param));
    }

    public static int min(List<List<Integer>> tra) {
        int[] arr = null;
        for (List<Integer> list : tra) {
            int[] tmp = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                if (arr == null) {
                    tmp[i] = list.get(i);
                    continue;
                }
                if (i - 1 < 0) {
                    tmp[i] = arr[i] + list.get(i);
                    continue;
                }
                if (i >= arr.length) {
                    tmp[i] = arr[i - 1] + list.get(i);
                    continue;
                }
                tmp[i] = Math.min(arr[i - 1], arr[i]) + list.get(i);
            }
            arr = tmp;
        }
        int min = Integer.MAX_VALUE;
        for (int i : arr) {
            min = Math.min(min, i);
        }
        return min;
    }
}
